package backTrack.review5_1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Class47 {
    List<List<Integer>>  result=new ArrayList<>();
    LinkedList<Integer> path=   new LinkedList<Integer>();
    boolean[] flag;
    public List<List<Integer>> permuteUnique(int[] nums) {
        flag=new boolean[nums.length];
        Arrays.fill(flag,false);
//        Arrays.sort(nums);
        if (nums.length==0){
            return result;
        }
        backTracking(nums);
        return result;
    }

    public void  backTracking(int[] nums){
        if (path.size()== nums.length){
            result.add(new ArrayList<>(path));
            return;
        }

        int[] used = new int[21];
        for (int i = 0; i < nums.length ; i++) {

            //  CKG TODO 2023/5/1: 同一层的去重中 使用了used数组 比使用布尔型数组要好
            if (used[nums[i]+10]==1){
//  CKG TODO 2023/5/1:  所以这个位置是 continue  为什么是continue呢  同一层中当发现第二次出现同一个元素时
//  CKG TODO 2023/5/1: 跳过这个元素 查找后面的元素 而不是break结束掉循环
                continue;
            }
            if (flag[i]){
                continue;
            }
            used[nums[i]+10]=1;
            flag[i]=true;
            path.add(nums[i]);
            backTracking(nums);
            path.removeLast();
            flag[i]=false;
        }
    }


    public static void main(String[] args) {
        Class47 class47 = new Class47();
        int[] arr={1,1,2};
        System.out.println(class47.permuteUnique(arr).toString());

    }


}
